'''
Created on May 20, 2009

@author: sternron
'''
from cliques.randomCliqueSearch import randomCliqueSearch
from cliques.brfsCliqueSearch import brfsCliqueSearch
from cliques.algorithmRunner import algorithmRunner
from cliques.potentialBasedTester import potentialBasedTester
from cliques.cliqueStarSearch import cliqueStarSearch
from cliques.knownDegreeSearch import knownDegreeSearch
from cliques.totalMembershipSearch import totalMembershipSearch
from cliques.probabilisticCliqueSearch import probabilisticCliqueSearch
from cliques.mdp.mdpBasedSearch import mdpBasedSearch
from cliques.mdp.heuristicMdp import heuristicMdp
from cliques.mdp.mdpLookahead import mdpLookahead
from cliques.mdp.limitedStatesMdp import limitedStatesMdp
import cliques.mdp.offlineMdpSolver
import cliques.mdp.dfsMdp
from cliques.mdp.limitedSampling import LimitedSampling
from cliques.mdp.rtdp import rtdp
import graphUtils.scaleFreeGenerator
from cliques.cliqueSearchLowerbound import CliqueSearchLowerbound
from cliques.mdp.offlineLimitedSampling import OfflineLimitedSampling
#from cliques.smartMdpBasedSearch import smartMdpBasedSearch
import cliques.mdp
import os
import graph
import random
import pickle
import time
import utils
from graph import readwrite
from cliques.cliqueFinder import cliqueFinder

import cProfile

def backup_old_file(output_file_name):
    BACKUP_DIR = "backup"
    if os.path.isdir(BACKUP_DIR)==False:
        os.mkdir(BACKUP_DIR)
    
    if os.path.isfile(output_file_name) == True:
        counter = 1
        backup_output_file = BACKUP_DIR+"\\"+output_file_name + str(counter) + ".backup"
        while os.path.isfile(backup_output_file):
            counter = counter + 1
            backup_output_file = BACKUP_DIR+"\\"+output_file_name + str(counter)
        
        os.rename(output_file_name, backup_output_file)

def write_header(out_file,file_header_fields):
    for column in file_header_fields:
        out_file.write("%s," % column)    
    out_file.write("\n")


def generate_graph(nodes,edges):
    new_graph = graph.graph()    
    new_graph.generate(nodes, edges)
    #new_graph = graphUtils.scaleFreeGenerator.createScaleFree(nodes, edges)
    return new_graph

def choose_start(ex_graph):
    nodes = ex_graph.nodes()
    return nodes[random.randint(0,len(nodes)-1)]

def create_algorithms():
    #return (randomCliqueSearch(),brfsCliqueSearch())
    #return (brfsCliqueSearch(),randomCliqueSearch(),cliqueStarSearch(),knownDegreeSearch())
    #return (knownDegreeSearch(),randomCliqueSearch(),cliqueStarSearch(),totalMembershipSearch(),probabilisticCliqueSearch())
    #return (knownDegreeSearch(),randomCliqueSearch(),cliqueStarSearch(),probabilisticCliqueSearch(),mdpBasedSearch())
    return (randomCliqueSearch(),knownDegreeSearch(),cliqueStarSearch(),\
#            mdpBasedSearch(rtdp,"RTDP-0-10",0,10),\
#            mdpBasedSearch(rtdp,"RTDP-0-20",0,20),\
#            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-0-500",0,500),\
#            mdpBasedSearch(Off lineLimitedSampling,"OfflineLimitedSampling-0-1000",0,1000),\
            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-3-10-0.5",3,10,noise=0.5),\
            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-3-50-0.5",3,50,noise=0.5),\
            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-3-100-0.5",3,100,noise=0.5),\
            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-3-250-0.5",3,250,noise=0.5),\
            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-3-500-0.5",3,500,noise=0.5),\
            mdpBasedSearch(OfflineLimitedSampling,"OfflineLimitedSampling-3-1000-0.5",3,1000,noise=0.5),\
            CliqueSearchLowerbound())
#            mdpBasedSearch(rtdp,"RTDP-0-080",0,80),\
#            mdpBasedSearch(rtdp,"RTDP-0-160",0,160),\
#            mdpBasedSearch(rtdp,"RTDP-0-320",0,320),\
#            mdpBasedSearch(rtdp,"RTDP-0-640",0,640))
#            mdpBasedSearch(cliq   ues.mdp.dfsMdp.dfsLookaheadMdp, "DFS-LH2",2))
#            mdpBasedSearch(cliques.mdp.dfsMdp.dfsLookaheadMdp, "DFS-LH2",2),\
#            mdpBasedSearch(cliques.mdp.dfsMdp.dfsLookaheadMdp, "DFS-LH3",3),\
#            mdpBasedSearch(cliques.mdp.dfsMdp.dfsLookaheadMdp, "DFS-LH4",4),\
#            mdpBasedSearch(cliques.mdp.dfsMdp.dfsLookaheadMdp, "DFS-LH5",5))
            #mdpBasedSearch(cliques.mdp.dfsMdp.dfsMdp, "DFS"))#,\
#            mdpBasedSearch(cliques.mdp.mdpLookahead.mdpLookahead,"lookaheadMdp",2),\
#            mdpBasedSearch(cliques.mdp.offlineMdpSolver.offlineMdpSolver,"offlineMdpSolver",2) )            
            
            
            

            #mdpBasedSearch(cliques.mdp.mdpLookahead.mdpLookahead,"lookaheadMdp-1",1))
#            mdpBasedSearch(rtdp, "RTDP-1-100",100 ,1,100),
#            mdpBasedSearch(rtdp, "RTDP-1-500",100 ,1,200),
#            mdpBasedSearch(rtdp, "RTDP-1-1000",100 ,1,300),
#            #mdpBasedSearch(rtdp, "RTDP-1-3000",100 ,1,3000),
#            mdpBasedSearch(rtdp, "RTDP-5-100",100 ,5,100),
#            mdpBasedSearch(rtdp, "RTDP-5-500",100 ,5,200),
#            mdpBasedSearch(rtdp, "RTDP-5-1000",100 ,5,300),
#            #mdpBasedSearch(rtdp, "RTDP-5-3000",100 ,5,3000),
#            mdpBasedSearch(rtdp, "RTDP-30-100",100 ,30,100),
#            mdpBasedSearch(rtdp, "RTDP-30-500",100 ,30,200),
#            mdpBasedSearch(rtdp, "RTDP-30-1000",100 ,30,300))
#            
#            #probabilisticCliqueSearch(),\
#            #mdpBasedSearch(cliques.mdp.mdpSolver.smartCliqueMdpSolver,"smart-MDP"),
#            #mdpBasedSearch(cliques.mdp.heuristicMdp.heuristicMdp,"heuristicMdp"),\
#            #mdpBasedSearch(cliques.mdp.mdpLookahead.mdpLookahead,"lookaheadMdp-0",0),
#            mdpBasedSearch(cliques.mdp.mdpLookahead.mdpLookahead,"lookaheadMdp-1",1),
#            #mdpBasedSearch(cliques.mdp.mdpLookahead.mdpLookahead,"lookaheadMdp-2",2),
#            mdpBasedSearch(limitedStatesMdp,"limitedStates",2))
#            #mdpBasedSearch(cliques.mdp.mdpLookahead.mdpLookahead,"mdpLookahead"))
#    #return (potentialBasedTester(),randomCliqueSearch())
#    #return (knownDegreeSearch(),cliqueStarSearch())

def main():
    results = dict()
    num_of_graphs=25
    iterations_per_graph=1
    min_k=5
    max_k=9
    node_range = [20,100,200,400,800]
#    min_nodes = 500
#    max_nodes = 2200
#    nodes_step = 300
    min_edges_factor = 8
    max_edges_factor = 16
    edges_step_factor = 4 
#    edge_step = 20
    clique_finder = cliqueFinder()
    runner = algorithmRunner()
    algorithms = create_algorithms()
    
    # Create results file 
    output_file_name = "result.csv"    
    backup_old_file(output_file_name)    
    out_file = open(output_file_name, "w")
    write_header(out_file,("k", "nodes", "edges", "alg.", "cost", "max_pdb", "max_gcn", "max_gen"))

    # Create results file 
    sum_file_name="summary.csv"
    backup_old_file(sum_file_name)
    sum_file = open(sum_file_name,"w")
    write_header(sum_file, ("k","nodes","edges","alg.","count","avg. cost","stdev"))
    current_graph_file = "current.graph"
    
    for nodes in node_range:
        #for edges in xrange(nodes*min_edges_factor,min(nodes*max_edges_factor,nodes*(nodes-1)/2),nodes*edges_step_factor):
        #for edges in xrange(nodes*min_edges_factor,min(nodes*max_edges_factor,nodes*(nodes-1)/2),nodes):
        for edges in xrange(nodes*min_edges_factor,min(nodes*max_edges_factor,(nodes*(nodes-1)/2)-1),nodes*edges_step_factor):
            for x in xrange(num_of_graphs):
                print "---- Building a graph[%d](%d,%d)... ----  " % (x,nodes,edges)        
                exp_graph = generate_graph(nodes,edges)                
                if os.path.isfile(current_graph_file):
                    os.remove(current_graph_file)
   
                utils.export_graph(exp_graph,current_graph_file)      
                exp_graph = utils.import_graph(current_graph_file)

                clique_finder.setup(exp_graph)
                                                   
                for graph_iteration in xrange(iterations_per_graph):    
                    start_node = choose_start(exp_graph)
                    
                    # Check if contains a k-clique is start_node's connected component
                    connected_comp = exp_graph.connected_components()
                    comp_index = connected_comp[start_node]
                    comp_items = [item for item in connected_comp.keys() if connected_comp[item]==comp_index]
                    k_clique_exist = True
                    for k in xrange(min_k,min(max_k,nodes)):
                        k_clique_exist = clique_finder.has_clique(k, comp_items)
                        if k_clique_exist:
                            for algorithm in algorithms:
                                current_config = (k,nodes,edges,algorithm)
                                if current_config not in results:
                                    results[current_config]=list()
                                            
                                algorithm.setup(exp_graph,k,start_node)
               
#                                profiler = cProfile.Profile()
#                                profiler.enable(subcalls=True, builtins=True)
                                #print "Start %d-clique search in graph(%d) from node %d" % (k,len(exp_graph.nodes()),start_node)
                                runner.run(algorithm)
#                                profiler.disable()
#                                profiler.print_stats("time")
                                
                                algorithm_iteration = algorithm.iteration
                                algorithm_done = algorithm.done
                                algorithm_statistics = algorithm.statistics()
                                print "%s - [%d] done, success=%s, alg.=%s, cost=%d" % (time.ctime(),graph_iteration,algorithm_done,algorithm,algorithm_iteration)
                                results[current_config].insert(0,algorithm_iteration)
                                for param in current_config:
                                    out_file.write("%s," % param)
                                out_file.write("%s," % algorithm_iteration)
                                for stat in algorithm_statistics:
                                    out_file.write("%s," % stat)
                                out_file.write("\n")
                                out_file.flush()
                        else:
                            break # No point in larger k since no k-cliques exists in the graph
            
            # Summarize data
            for k in xrange(min_k,min(max_k,nodes)):
                for algorithm in algorithms:
                    current_config = (k,nodes,edges,algorithm)
                    if results.has_key(current_config):
                        count = len(results[current_config])                    
                        avg_result = float(sum(results[current_config]))/count
                        stdev_result = utils.stdev(results[current_config])
                        for param in current_config:
                            sum_file.write("%s," % param)                    
                        sum_file.write("%d,%f,%f\n" % (count,avg_result,stdev_result))
            sum_file.flush()
            
    
    out_file.close()
    sum_file.close()

if __name__ == '__main__':
    main()